The present invention relates generally to interconnection circuitry, and more particularly to a system for handling data within a network of computer system components in a manner that a plurality of data sources can transfer information to a plurality of destinations simultaneously.
The typical computer system uses a busing arrangement as its primary interconnection to transfer information from one component of the system to another. In such a system, a component, such as a central processor, directs information to another component, such as a memory chip, by placing the address to which the information is directed on the system address bus and the information on the system data bus. The destination for the information recognizes an address within its range of addresses and accepts the information available on the data bus. Each of these buses are made up of a number of conductors (for example, 32) which physically connect to each of the system components.
During the time that any particular source of information is using the system address and data buses, they are unavailable for use by any other source since all of the conductors of each bus available to carry either address or data information are occupied. In the past, busing arrangements have sufficed for transferring information in a typical personal computer or work station. However, functions such as the presentation of animated graphics and television involve the transfer of so much information that they tend to require an entire system to be devoted to their use. When it is desired to incorporate a number of these functions into the same computer system and run multiple operations simultaneously, a busing arrangement is incapable of handling the load.
To overcome the limitations of the aforementioned busing arrangement, various ring interconnection arrangements have been suggested. In these ring interconnection arrangements, each system component is directly connected by one-way connection paths to receive information from one other single system component and to send information to another single system component, thereby isolating each component from all but two other components. Each component forwards information around the ring until the information arrives at its destination. Even if the available bandwidth on each one-way connection in a ring is no greater than that available in a system data bus, the ring arrangement increases the amount of information that can be transferred because a number of sources of information can communicate with a number of destinations simultaneously.
Most ring-type systems suggested to date have retry systems where one system component places a packet of information on the ring addressed to another component. If the addressed component cannot handle the incoming information, it places a retry command on the ring. This causes the operation to be terminated, the transmitted information to be dumped, and the packet to be resent after some delay. Thus, the retry operation inherently slows the system when the amount of traffic on the system approaches saturation.
To overcome the problems of retry ring systems and to provide a system capable of transferring much more data than conventional computer arrangements, a new interconnect has been devised which is the subject of U.S. Pat. No. 5,165,024, entitled "Information Transfer and Receiving System With a Ring Interconnect Architecture Using Voucher and Ticket Signals", P. Sweazey, issued Nov. 17, 1992, and assigned to the assignee of this invention; U.S. Pat. No. 5,165,019, entitled "Ring Interconnect System Architecture", P. Sweazey, issued Nov. 17, 1992, and assigned to the assignee of this invention; U.S. patent application Ser. No. 530,096, entitled "Improved Ring System Interconnect Architecture", P. Sweazey, filed on May 29, 1990, and assigned to the assignee of this invention; and U.S. patent application Ser. No. 08/026,969, entitled "Economical Payload Routing in a Multiple-Ring Network", P. Sweazey, filed on Mar. 3, 1993, and assigned to the assignee of this invention. The entire disclosures of these two patents and two patent applications are hereby incorporated by reference.
This new interconnect in its basic form is made up of a plurality of nodes, each such node being associated with at least one of a plurality of computer system components. The computer system component or components associated with the node is referred to as the "client" of the node. The nodes are connected in a unidirectional ring with transmission paths connecting each node to one node which is a source of information (a "source node"), and to another node which is a recipient of information (a "target node"). A plurality of unidirectional rings may be interconnected by using individual ring nodes to create bridges connecting separate rings. This creates a local area network of unidirectional rings.
This new interconnect is typically used as a secondary connection between the components of a computer system. The primary connection between these components is usually a busing arrangement such as the NuBus manufactured and used by Apple Computer, Inc., in its line of Apple Macintosh II personal computers.
Each node in a unidirectional ring includes apparatus for receiving information from and transferring information to its associated client. When a node's associated client desires to transfer information to another client of a different node, the client causes its associated node to generate and place a voucher signal on the transmission path to indicate that the node has information to be transmitted to another client component.
Each node includes storage space for information and apparatus which responds to the receipt of a voucher signal directed to it for determining whether the node is able to store information in its storage space. Each node also includes apparatus which responds to a determination by its client that storage space is available by placing a ticket signal on the transmission path (directed to the node which is to be the source of the information) to indicate that storage space is available.
When a source node receives such a ticket signal, it causes the information packet to be launched on the transmission path. In this manner, no information is propagated on the transmission path until space is available for it at the target node, and delays due to information rejection at the target node are eliminated.
Each node also includes circuitry to relay voucher signals, ticket signals, and information directed to another node, so that the information, voucher or ticket is passed along the transmission path to the correct node. Moreover, each node includes apparatus for assuring that both voucher and ticket signals are transferred by the node in preference to any information. By this means, the transferred information on the transmission path does not get in the way of and delay the signals which control the transmission of that information.
The transfer of information among nodes in various rings requires that each node in a ring have a unique address, or ID, in that ring. To do this, one node in a ring is designated as the ring master, and all other nodes on the ring are configured as slaves.
During initialization of the ring, special symbols are circulated around the ring to assign node ID numbers to each node. The master node assigns itself to be node 0. The master then begins to transmit a stream of identical symbols at the downstream port whose high-order four bits are [0,0,0,0]. The first slave node to receive this symbol increments the value to [0,0,0,1] and becomes node 1. Each slave node in turn increments the value and takes on its own unique node ID. When the master node receives the symbol at its upstream port, the value of the symbol is the largest ID number in the ring. The master node stores this value and forwards it around the ring, so that each node in the ring knows the total number of nodes in the ring.
In a multiple ring network, each ring contains one or more nodes that act as bridges to connect with other rings. These nodes are called bridge nodes. Unlike the other nodes in a ring, which are called leaf nodes, the bridge nodes do not receive or transmit information to associated client components. Instead, each bridge node is connected to another bridge node on a separate ring. The separate ring may include a combination of bridge nodes and leaf nodes, or may only contain bridge nodes.
The performance of various functions in a multiple ring network often requires client components in separate rings to exchange information in a back-and-forth fashion. A routing symbol is required to transfer data from a node which is a source of information (a "source node") to a node which is a recipient of information (a "target node"). A separate routing symbol is required to transfer data or control signals from the target node back to the source node. These control signals may instruct the source node to halt, resume, accelerate, or decelerate data transmission to the target node. Since the target node may not know the location in the network of the source node, the source node must provide both the routing symbol from the source node to the target node, and the return routing symbol from the target node to the source node.
The above-described network is actually a highly-distributed switching fabric. One client of a leaf node in one ring may establish a connection with any other leaf node (box, card or chip) in the fabric. It may send a data stream to the target node without having any knowledge of other network protocols that may be in use by other nodes.
However, a source node must know the precise physical path to the target, must be able to request bandwidth allocation from a bandwidth management facility which understands the capacities and limitations of all data paths, and must conform to the limits of bandwidth consumption allocated through that central facility. In addition, the total system must be capable of handling the dynamic addition or deletion of any portion of the fabric. It is therefore necessary that a method exist to dynamically discover the topology of the fabric at any time, and to detect if a change to the previously-assumed topology occurs.
Accordingly, an object of the present invention is to allow a source node in one ring of a multiple ring network to discover the topology of a network of rings interconnected by bridges.
Another object of the present invention is to allow a bridge node to route any topology-discovery symbol based only on knowledge of the bridge node's own local node address, without regard to the extent, complexity, or redundancy of the total multiple-ring topology.
A further object of the present invention is to allow all routing information to be contained within a single routing symbol.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out in the claims.